Để giải bài toán 4 màu, các nhà toán học đã tìm cách xây dựng các đồ thị tương ứng với các bản đồ và đưa giả thuyết 4 màu về giả thuyết số màu của đồ thị phẳng.

Với mỗi bản đồ, ta có thể định nghĩa một đồ thị:

• Tập đỉnh: gồm các đỉnh mà mỗi đỉnh tương ứng với một nước trên bản đồ;
• Tập cạnh: mỗi cạnh tương ứng với 2 nước kề nhau có chung một biên giới.

Ví dụ: Hình minh họa đồ thị (G) tương ứng với bản đồ Giả thuyết minh họa đồ thị (G) bên cạnh.

Mỗi vùng được ký hiệu bằng một chữ cái, các chữ này cũng được dùng để ký hiệu các đỉnh của đồ thị.

Từ ví dụ này ta thấy yêu cầu hai nước kề nhau phải có màu khác nhau khi tô bản đồ cũng tương ứng với yêu cầu hai đỉnh kề nhau phải có màu khác nhau khi thực hiện phép tô màu đỉnh cho đồ thị.

Các nhà toán học đã chứng minh được định lý sau đây:

Định lý: Đồ thị (G) được định nghĩa tương ứng với mỗi bản đồ M (theo như định nghĩa trên) luôn là đồ thị phẳng. Cách tô màu mỗi vùng của bản đồ M tương ướng với cách tô màu các đỉnh của đồ thị (G)

Nhờ định lý trên, giả thuyết 4 màu được quy về giả thuyết về số màu của đồ thị phẳng được phát biểu như sau:

Giả thuyết:

Mọi đồ thị phẳng (G) đều có số màu γ(G)≤4

Sau công trình của Kenneth Appel, Wolfgang Haken và John A. Koch thì giả thuyết trên đã trở thành định lý và ngày nay chúng ta cũng gọi là định lý 4 màu.

Cho đến bây giờ cũng chưa tìm được cách chứng mình định lý 4 màu mà không dùng kiểm chứng bằng máy tính. Một số công trình khác cũng tìm cách cải tiến thuật toán kiểm tra để chạy nhanh hơn.